1. Field of the Invention
The present invention pertains to the field of digital communications. More particularly, this invention relates to a system and method for static and dynamic scheduling of outbound communication cells in an asynchronous transfer mode communication network.
2. Background
Packet switching communication networks are commonly employed to transfer digital information over long distances. Packet switching networks are also referred to as cell switching communication networks. One such type of network is an asynchronous transfer mode communication network. Such an asynchronous transfer mode communication network enables the transfer of digital voice information, digital video information, and digital data over short or long distances. Such a communication network enables a variety of communication devices to share a common carrier communication link on a demand driven basis.
Typically, a communication path through an asynchronous transfer mode communication network is referred to as a virtual circuit. A typical physical communication link in such a communication network is usually shared among a set of virtual circuits. A typical high speed physical communication link in such a network usually provides sufficient bandwidth to support a large number of virtual circuits. A communication service subscriber in such a system usually contracts with a common carrier service provider to specify the bandwidth utilization of the virtual circuits on the physical communication links provided by the common carrier.
A communication service subscriber on an asynchronous transfer mode communication network typically selects from among a variety of differing data services having differing bandwidth parameters. Such differing data services typically include constant bit rate (CBR) services and variable bit rate (VBR) services. An example application of a constant bit rate data service is a data service that supports a real time audio or video data link. An example application of a variable bit rate data service is a bursty data service for a local area network that provides electronic mail services.
Typically, the communication service subscriber provides a communication controller coupled to one or more of the common carrier physical communication links. Such a communication controller typically schedules outbound communication cells for each virtual circuit and transmits the outbound communication cells over the common carrier communication links.
Such a communication controller typically transmits outbound communication cell traffic according to predefined data rates specified in a data service contract. For example, a communication service subscriber may contract for a maximum data rate and a minimum data rate for variable bit rate virtual circuits. The communication service subscriber typically contracts for fixed data rates on the constant bit rate virtual circuits.
As a consequence, a communication controller for such an asynchronous transfer mode communication network must typically observe a set of bandwidth allocation parameters for each virtual circuit supported by the communication controller. For example, a constant bit rate virtual circuit typically transmits communication cells over the communication network at regular intervals while the virtual circuit is active. In addition, such constant bit rate data services are relatively intolerant of delays in communication cell transmission over the network. On the other hand, variable bit rate virtual circuits typically have a contracted guaranteed minimum data rate and a maximum of burst data rate. A communication controller that supports such data services must schedule outbound traffic to prevent delays in constant bit rate traffic and to observe the contract requirements for variable bit rate traffic while providing maximum bandwidth utilization allowed by the contract.
All communication controllers for such an asynchronous transfer mode communication network subdivide outbound data transmission on a common carrier communication link into a series of cell slots. The duration of each cell slot varies according to the bandwidth of the physical communication link. For example, a physical communication link having a bandwidth of 155 megabits per second is subdivided into cell slots each having a 2.7 microsecond duration.
Typically, a communication controller schedules outbound communication cell traffic by selecting a communication cell for transmission during each cell slot according to the availability of outbound data for each virtual circuit and the bandwidth allocation parameters for each virtual circuit. During each cell slot, a cell scheduler of the communication controller typically selects a virtual circuit from among active virtual circuits that provides data for the next outbound cell slot. Typically, such a cell scheduler interleaves data from each of the active virtual circuits according to the bandwidth allocation parameters. Such a cell scheduler usually allocates cell slots at regular intervals to the constant bit rate virtual circuits. Such a cell scheduler typically allocates the remaining cell slots to the variable bit rate virtual circuits.
Prior communication controllers for such communication networks typically employ dedicated specialized processors to perform cell scheduling and cell assembly functions. Such a dedicated specialized processor is typically required because a high bandwidth common carrier communication link provides minimal cell slot duration. For example, a communication link having a data rate of 155 megabits per second requires that a cell scheduling decision and cell assembly operation be rendered during each cell slot interval of 2.7 microseconds. Unfortunately, such highly specialized dedicated processors greatly increase the cost of such prior communication subsystems.
In addition, prior lower cost communication controllers commonly perform cell scheduling by providing timer circuits for each constant bit rate virtual circuit. Typically in such systems, the timer circuits are preprogrammed with timer values that correspond to the bandwidth of the constant bit rate virtual circuits. Such timer circuits usually count the cell slot intervals on the physical communication link. Typically, an expired timer indicates that the corresponding constant bit rate virtual circuit requires scheduling of an outbound communication cell. Such prior systems usually provide a limited number of timer circuits in order to limit overall system cost. Unfortunately, such a limited number of timer circuits imposes a fixed upper limit to the number of constant bit rate virtual circuits supported in such a prior communication controller.